#include <stdio.h>
#include <windows.h>
#include <time.h>
#include "sudoku_new.h"

extern int normal[MAXNU];

//用于储存记录所有空单元的解集
extern int all[MAXNU*MAXNU][MAXNU];

#ifdef AUTO
int sudoku[MAXNU][MAXNU] = {
        {9,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0},{0,0,0,0,6,0,0,0,0},{0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,3,0,0},{0,0,0,0,9,0,0,0,0},{0,0,0,0,0,0,0,0,0}
        /**
         {0,0,5,3,0,0,0,0,0},{8,0,0,0,0,0,0,2,0},{0,7,0,0,1,0,5,0,0},
         {4,0,0,0,0,5,3,0,0},{0,1,0,0,7,0,0,0,6},{0,0,3,2,0,0,0,8,0},
         {0,6,0,5,0,0,0,0,9},{0,0,4,0,0,0,0,3,0},{0,0,0,0,0,9,7,0,0}
          **/
        /**
        {5,3,6,4,1,2,9,8,7},{4,7,9,6,8,5,1,3,2},{8,2,1,9,7,3,4,5,6},
        {9,8,7,3,4,6,5,2,1},{6,5,3,1,2,7,8,4,9},{2,1,4,8,5,9,7,6,3},
        {3,4,5,7,6,1,2,9,8},{1,6,8,2,9,4,3,7,5},{7,9,2,5,3,8,6,1,4}
         **/

        /**
        {0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}
         **/

        /*
         6  7  8    3  1  5    9  2  4
         5  3  4    8  2  9    7  1  6
         2  9  1    6  4  7    5  3  8

         9  8  6    1  5  3    4  7  2
         1  4  5    7  6  2    3  8  9
         3  2  7    4  9  8    6  5  1

         4  6  2    5  3  1    8  9  7
         8  5  9    2  7  4    1  6  3
         7  1  3    9  8  6    2  4  5
         * */
};
#endif

#ifndef AUTO
int sudoku[MAXNU][MAXNU] = {0};
#endif

#ifndef TEST

int main() {

    clock_t start, finish;  //定义第一次调用CPU时钟单位的实际，可以理解为定义一个计数器
    double Total_time;      //定义一个double类型的变量，用于存储时间单位
    start = clock();        //获取进入要测试执行时间代码段之前的CPU时间占用值

#ifndef AUTO
    //输入整个数独
    for (int i = 0; i < MAXNU; ++i) {
        for (int j = 0; j < MAXNU; ++j) {
            printf("Please input x: = %d\ty: = %d\n",i+1,j+1);
            scanf("%d",&sudoku[i][j]);
        }
    }
#endif

    printf("Input:\n");
    output_sudoku(sudoku);

    //用于临时记录的缓存一维数组
    int res[MAXNU] = {0};
    //用于储存记录所有的空单元及其位置
    int zer[MAXNU*MAXNU][3];

    //用于临时记录的所有空单元的解集 试错缓存记录
    int all_temp[MAXNU*MAXNU][MAXNU] = {0};

    //用于计数的整型变量
    int count = 0,cnt = 0;
    //用于临时储存空单元坐标的结构体
    Local loc_temp;

    //找到所有空单元将位置返回给zer[][] 数量返回给count
    count = find_all_zero(sudoku,zer);

    //用于填入非空解集的标志位
    short flag = 1;

    if(is_input_error(sudoku)){ //当输入有错误时
        printf("Mabe your input had PROBLEM!\n");   //打印提示
        return 0;
    }

    //当suduku还有空的单元时 执行求解步骤
    while (had_zero_uint(sudoku)){

        //找空单元坐标 (x+1,y+1)
        loc_temp = find_zero_local(sudoku);

#ifdef DEBUG
        //打印找到的空单元坐标 用作数组坐标时需要 x-1,y-1
        printf("\nloc_temp:(%d,%d)\n",loc_temp.x-1,loc_temp.y-1);
#endif

        //当前坐标为第cnt个空单元 (x+0,y+0)
        cnt = local_find_count(loc_temp.x-1,loc_temp.y-1,zer);

#ifdef DEBUG
        //打印第cnt个空单元序号
        printf("No.cnt: %d\n",cnt);
#endif
        //标志位决定是否执行这一步骤
        if(flag){

            //求解集 (x+1,y+1)
            resolve_sudoku(sudoku,loc_temp.x,loc_temp.y,res);

            //储存在all_temp[][]里
            write_one_to_two(cnt-1,res,all_temp);

            //清空标志
            flag = 0;
        }

#ifdef DEBUG
        //打印is_nop_arr的值
    printf("is_nop_arr: %d\n",is_nop_arr(all_temp[cnt-1]));
#endif

        if(!is_nop_arr(all_temp[cnt-1])){   //解集非空


            //填解
            sudoku[loc_temp.x-1][loc_temp.y-1] = all_temp[cnt-1][0];

#ifdef DEBUG
            //打印数独中的某个单元和所填的解
            printf("sudoku[%d][%d] = %d\n",loc_temp.x-1,loc_temp.y-1,res[0]);
#endif

            //需要另外执行步骤 将标志位打开
            flag = 1;

        }else{  //解集为空

                if(cnt-1 == 0){ //cnt为第一个空单元

                    printf("OOPS!\n");
                    break;

                } else{ //cnt不是第一个空单元

                //找到上个空单元的坐标 (x+0,y+0)
                loc_temp = count_find_local(zer,cnt-1);

#ifdef DEBUG
                //打印上个空单元的坐标
                printf("last_local:(%d,%d)\n",loc_temp.x,loc_temp.y);
#endif

                //删除该单元下的第一个解 (cnt+1)
                delete_one_key(cnt-1-1,all_temp,all_temp);

#ifdef DEBUG
                printf("DELETE all_temp[%d]\n",cnt-1);
                print_arr(all_temp[cnt-1-1]);
#endif

                //把当前坐标的数独值删去
                sudoku[loc_temp.x][loc_temp.y] = 0;

            }

        }
    }

    //当sudoku没有空单元的时候 判断是否满足数独条件
    if(is_sudoku(sudoku)){
        printf("Result:\n");
        output_sudoku(sudoku);
    } else{ //当sudoku不满足数独条件的时候 打印并显示结果
        printf("Failed:\n");
        output_sudoku(sudoku);
    }

    finish = clock();
    Total_time = (double)(finish - start) / CLOCKS_PER_SEC;    //单位换算，换算成毫秒
    printf("Time:%0.3fs\n",Total_time);
    system("pause");
    return 0;
}

#endif


#ifdef TEST

int main()
{
//    int res[MAXNU*MAXNU][MAXNU] = {0};
//
//    resolve_all_arr(sudoku,res);
//
//    outprint_arr(MAXNU*MAXNU,MAXNU,res);
//
//    delete_one_key(1,res,res);
//
//    printf("\n");
//
//    outprint_arr(MAXNU*MAXNU,MAXNU,res);

//
//    if(is_input_error(sudoku)){
//
//        printf("Mabe your input had PROBELEM!\n");
//
//    }

    input_sudoku_new(sudoku);
    output_suduku(sudoku);

    return 0;
}

#endif
